package letcode.oneQuestionPerDay._202003._20200321;

import java.util.*;

/**
 * @author 许群星
 * @decription 水壶问题   BFS 广度优先
 * @data 2020/3/218:20
 **/
public class WaterAndJugProblem_2 {
    public static void main(String[] args) {
//        int x=3,y=5,z=4;
//        int x=2,y=6,z=5;
        int x = 1, y = 2, z = 3;
        System.out.println(canMeasureWater(x, y, z));
    }

    //提供方法
    /*
    可以使用一个队列维护需要扩散的点，以及一个set或者数组维护已经被访问过的点来实现：

    初始时，队列和set均为空。将起始点放入队列及set。
    如果队列为空则 bfs 结束。
    弹出队首元素并访问其周围元素，设为 p。
    如果p为目标状态则 bfs 结束。
    访问 p 周围的元素，将不在set中的元素放入队列及set。跳转第 2 步。
     */
    public static boolean canMeasureWater(int x, int y, int z) {
        //边界情况
        if (z == 0)
            return true;
        if (x + y < z)
            return false;

        //BFS
        Queue<Map.Entry<Integer, Integer>> queue = new ArrayDeque<>();
        AbstractMap.SimpleEntry<Integer, Integer> start = new AbstractMap.SimpleEntry<>(0, 0);
        queue.add(start);

        Set<Map.Entry<Integer, Integer>> visiter = new HashSet<>();
        visiter.add(start);

        while (!queue.isEmpty()) {
            Map.Entry<Integer, Integer> entry = queue.poll();
            int curX = entry.getKey();
            int curY = entry.getValue();

            //目标情况
            if (curX == z || curY == z || curX + curY == z)
                return true;

            //过程
            if (curX == 0)//装满第一个桶
                addIntQueue(queue, visiter, new AbstractMap.SimpleEntry<>(x, curY));
            if (curY == 0)//装满第二个桶
                addIntQueue(queue, visiter, new AbstractMap.SimpleEntry<>(curX, y));
            if (curY < y)//把第一个桶倒空
                addIntQueue(queue, visiter, new AbstractMap.SimpleEntry<>(0, curY));
            if (curX < x)//第二个桶倒空
                addIntQueue(queue, visiter, new AbstractMap.SimpleEntry<>(curX, 0));

            //y-curY是第二个桶还可以加的水的升，但是最多只能在家curX
            int moveSize = Math.min(curX, y - curY);
            //把第一个桶里的curX升水倒入第二个桶
            addIntQueue(queue, visiter, new AbstractMap.SimpleEntry<>(curX - moveSize, curY + moveSize));
            //y-curY是第二个桶还可以加的水的升，但是最多只能在家curY
            moveSize = Math.min(curY, x - curX);
            //把第一个桶里的curX升水倒入第二个桶
            addIntQueue(queue, visiter, new AbstractMap.SimpleEntry<>(curX + moveSize, curY - moveSize));

        }

        return false;
    }

    //把桶装满
    private static void addIntQueue(Queue<Map.Entry<Integer, Integer>> queue,
                                    Set<Map.Entry<Integer, Integer>> visited,
                                    Map.Entry<Integer, Integer> newentry) {
        if (!visited.contains(newentry)) {
            visited.add(newentry);
            queue.add(newentry);
        }
    }

}
/*
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example)

输入: x = 3, y = 5, z = 4
输出: True
示例 2:

输入: x = 2, y = 6, z = 5
输出: False
 */